/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
    {
        ListNode* cur1 = headA, * cur2 = headB;
        queue<ListNode*> st1, st2;
        int len1 = 0, len2 = 0;
        while (cur1 != nullptr)
        {
            len1++;
            st1.push(cur1);
            cur1 = cur1->next;
        }

        while (cur2 != nullptr)
        {
            len2++;
            st2.push(cur2);
            cur2 = cur2->next;
        }

        if (st1.size() < st2.size()) st1.swap(st2);

        int gap = st1.size() - st2.size();

        while (gap--) st1.pop();


        while (!st1.empty())
        {
            if (st1.front() == st2.front())return st1.front();

            st1.pop(), st2.pop();
        }
        return nullptr;
    }
};